/**
 * 
 */
package solution.string;

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

import junit.framework.Assert;

import org.junit.Test;

/**
 * @author <a href="www.sureinterview.com">SureInterview</a>
 */
public class WordsSentence {

	/**
	 * version ONE. two passes. </br> 1. reverse the whole string. </br> 2.
	 * reverse each word.
	 */
	class RansomNote {
		boolean checkRansomNote(String paragraph, String notes) {
			if (paragraph == null)
				return false;

			if (notes == null)
				return true;

			// get the needed words for ransom.
			Map<String, Integer> wordCol = getWords(notes);

			sbuf = paragraph.toCharArray();
			int convStart = -1, convEnd = -1;
			for (int i = 0; i <= sbuf.length; i++) {
				if (!isAlpha(i - 1) && isAlpha(i)) {
					// find ...@A...
					convStart = i;
				} else if (!isAlpha(i) && isAlpha(i - 1)) {
					// find ...A@...
					convEnd = i - 1;
					String wd = String.valueOf(sbuf, convStart, convEnd
							- convStart + 1);

					// check the current word.
					if (!wordCol.containsKey(wd)) {
						continue;
					}

					// the current word is useful, update the collection
					int count = wordCol.get(wd) - 1;
					if (count == 0) {
						wordCol.remove(wd);
						if (wordCol.isEmpty())
							return true;
					} else {
						wordCol.put(wd, count);
					}
				}
			}

			// NOTE: make sure all words are handled, especially the first word
			// and the last word.
			return false;
		}
	}

	interface ReverseWordsInSentence {
		String reverse(String sentence);
	}

	/**
	 * version ONE. two passes. </br> 1. reverse the whole string. </br> 2.
	 * reverse each word.
	 */
	class RW1 implements ReverseWordsInSentence {
		@Override
		public String reverse(String sentence) {
			if (sentence == null)
				return null;

			if (sentence.length() < 2)
				return sentence;

			sbuf = sentence.toCharArray();

			// reverse the whole string first.
			for (int p = 0, q = sbuf.length - 1; p < q; p++, q--) {
				swap(p, q);
			}

			// reverse each word again.
			int convStart = -1, convEnd = -1;
			for (int i = 0; i <= sbuf.length; i++) {
				if (!isAlpha(i - 1) && isAlpha(i)) {
					// find ...@A...
					convStart = i;
				} else if (!isAlpha(i) && isAlpha(i - 1)) {
					// find ...A@...
					convEnd = i - 1;
					for (int p = convStart, q = convEnd; p < q; p++, q--) {
						swap(p, q);
					}
				}
			}

			// NOTE: make sure all words are reversed, especially the first word
			// and last word.
			return String.valueOf(sbuf);
		}
	}

	char[] sbuf;

	public Map<String, Integer> getWords(String sentence) {
		if (sentence == null)
			return null;

		sbuf = sentence.toCharArray();
		Map<String, Integer> mp = new HashMap<String, Integer>();

		int convStart = -1, convEnd = -1;
		for (int i = 0; i <= sbuf.length; i++) {
			if (!isAlpha(i - 1) && isAlpha(i)) {
				// find ...@A...
				convStart = i;
			} else if (!isAlpha(i) && isAlpha(i - 1)) {
				// find ...A@...
				convEnd = i - 1;
				String wd = String.valueOf(sbuf, convStart, convEnd - convStart
						+ 1);
				int count = 1;
				if (mp.containsKey(wd)) {
					count = mp.get(wd) + 1;
				}
				mp.put(wd, count);
			}
		}

		// NOTE: make sure all words are handled, especially the first word
		// and the last word. Check isAlpha to see how it is handled.
		return mp;
	}

	/**
	 * check if sub[i] is a alphabet.
	 * 
	 * @param i
	 * @return
	 */
	boolean isAlpha(int i) {
		// Note: the code takes advantage of this definition.
		if (i < 0 || i >= sbuf.length)
			return false;

		int c = sbuf[i];
		if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z')
			return true;
		return false;
	}

	void swap(int p, int q) {
		char c = sbuf[p];
		sbuf[p] = sbuf[q];
		sbuf[q] = c;
	}

	@Test
	public void za_testRansom() {
		String[][] testyes = new String[][] {
				//
				{ "aa bb ee", "aa aa bb aa bb cc dd ee" }, //
				{ "aa aa aa", "aa aa bb aa bb cc dd ee" }, //
				{ "bb aa bb", "aa aa bb aa bb cc dd ee" }, //
				{ "aa bb bb", "aa aa bb aa bb cc dd ee" }, //
		};
		String[][] testno = new String[][] {
				//
				{ "dd dd dd", "aa bb aa bb cc aa bb cc dd ee" }, //
				{ "aa bb ff", "aa bb aa bb cc aa bb cc dd ee" }, //
				{ "dd ee ff", "aa bb aa bb cc aa bb cc dd ee" }, //
		};

		RansomNote rn = new RansomNote();
		for (String[] tt : testyes) {
			Assert.assertTrue(rn.checkRansomNote(tt[1], tt[0]));
		}
		for (String[] tt : testno) {
			Assert.assertFalse(rn.checkRansomNote(tt[1], tt[0]));
		}
	}

	@Test
	public void za_testReverseSentence() throws IOException {
		String[] test = new String[] {
				//
				"this is a test", //
				"@@@this is a test", //
				"this is a test@@", //
				"this-is?a.test?", //
		};

		ReverseWordsInSentence rs = new RW1();
		for (String element : test) {
			System.out.println(rs.reverse(element));
		}
	}
}
